package leetcode._08_dynic;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author pppppp
 * @date 2022/3/24 15:04
 * 有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
 * 每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
 * 如果 x == y，那么两块石头都会被完全粉碎；
 * 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
 * 最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。
 * <p>
 * 示例 1：
 * 输入：stones = [2,7,4,1,8,1]
 * 输出：1
 * 解释：
 * 组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
 * 组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
 * 组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
 * 组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。
 * <p>
 * 示例 2：
 * 输入：stones = [31,26,33,21,40]
 * 输出：5
 * <p>
 * 示例 3：
 * 输入：stones = [1,2]
 * 输出：1
 * <p>
 * 提示：
 * 1 <= stones.length <= 30
 * 1 <= stones[i] <= 100
 */
public class _1049_最后一块石头的重量II {
    @Test
    public void T_0() {
        int[][] nums = {{91}, {1, 2, 4, 8, 16, 32, 64, 12, 25, 51}, {2, 7, 4, 1, 8, 1}, {31, 26, 33, 21, 40}, {1, 2}};
        int[] ans = {91, 1, 1, 5, 1};
        for (int i = 0; i < nums.length; i++) {
            // System.out.println(lastStoneWeightII_0(nums[i]) == ans[i]);
            // System.out.println(lastStoneWeightII_11(nums[i]) == ans[i]);
            // System.out.println(lastStoneWeightII_1(nums[i]) == ans[i]);
            System.out.println(lastStoneWeightII_review(nums[i]) == ans[i]);
        }
    }

    public int lastStoneWeightII_review(int[] stones) {
        if(stones.length <2){
            return stones.length == 0 ? 0 : stones[0];
        }
        int sum = Arrays.stream(stones).sum();
        int target = sum / 2;
        int[][] dp = new int[stones.length][target + 1];
        Arrays.fill(dp[0], stones[0]);
        for (int i = 0; i < target; i++) {
            if (i < stones[0]) {
                dp[0][i] = 0;
            } else {
                break;
            }
        }

        for (int i = 1; i < stones.length; i++) {
            for (int j = 1; j <= target; j++) {
                if (j >= stones[i]) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - stones[i]] + stones[i]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return sum - 2 * dp[stones.length - 1][target];
    }

    /*1.转化为背包问题 将石头分为质量尽量相等的两堆 背包的容量为 sum/2,res = dp[stone.len-1][sum/2],ans = sum-2*res */
    public int lastStoneWeightII_1(int[] stones) {
        if (stones.length == 1) {
            return stones[0];
        }
        int sum = Arrays.stream(stones).sum();
        int target = sum / 2;
        int[][] dp = new int[stones.length][target + 1];
        /*初始化dp*/
        Arrays.fill(dp[0], stones[0]);
        for (int i = 0; i < stones[0]; i++) {
            dp[0][i] = 0;
        }
        for (int i = 1; i < stones.length; i++) {
            for (int j = 1; j <= target; j++) {
                if (j >= stones[i]) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - stones[i]] + stones[i]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return sum - 2 * dp[stones.length - 1][target];
    }

    /*1.空间优化*/
    public int lastStoneWeightII_11(int[] stones) {
        if (stones.length == 1) {
            return stones[0];
        }
        int sum = Arrays.stream(stones).sum();
        int target = sum / 2;
        int[] dp = new int[target + 1];
        /*初始化dp*/
        Arrays.fill(dp, stones[0]);
        for (int i = 0; i < stones[0]; i++) {
            dp[i] = 0;
        }
        for (int i = 1; i < stones.length; i++) {
            /*此时要从大到小进行，不然会覆盖可能需要用到的较小值*/
            for (int j = target; j >= 1; j--) {
                if (j >= stones[i]) {
                    dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
                }
            }
        }
        return sum - 2 * dp[target];
    }

    /*0.思路错误的尝试*/
    public int lastStoneWeightII_0(int[] stones) {
        d(stones, 0);
        return stones[stones.length - 1];
    }

    private void d(int[] stones, int sIndex) {
        Arrays.sort(stones);
        if (sIndex == stones.length - 1) {
            return;
        }
        int n = stones.length - sIndex;
        if (n % 2 == 0) {
            int j = sIndex;
            while (j < stones.length - 1) {
                stones[j] = stones[j + 1] - stones[j];
                stones[j + 1] = 0;
                j += 2;
            }
            d(stones, sIndex + n / 2);
        } else {
            stones[0] = stones[n - 1] - stones[0];
            stones[n - 1] = 0;
            d(stones, sIndex + 1);
        }
    }
}
